import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Solution {
    public void reorderList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast == null) {
            ListNode cur = slow;
            while (cur != null) {
                stack.push(cur);
                cur = cur.next;
            }
        } else {
            ListNode cur = slow.next;
            while (cur != null) {
                stack.push(cur);
                cur = cur.next;
            }
        }
        ListNode cur = head;
        while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        slow.next = null;
        // return head;
    }
}
